package comprehensive;

import java.util.ArrayList;
import java.util.List;

public class Exercises5 {
    // 77、组合
    int end;
    int len;
    List<List<Integer>> ret;
    List<Integer> path;

    public List<List<Integer>> combine(int n, int k) {
        end = n;
        len = k;
        ret = new ArrayList<>();
        path = new ArrayList<>();

        dfs(1);

        return ret;
    }

    public void dfs(int start) {

        if (len == path.size()) {
            ret.add(new ArrayList<>(path));
            return;
        }

        // 每次for循环都上一个位置的下一个开始
        for(int i = start;i <= end;i++) {
            path.add(i);

            dfs(i + 1);

            path.remove(path.size() - 1);
        }
    }
}
